/*
 * @lc app=leetcode.cn id=494 lang=cpp
 *
 * [494] 目标和
 */

// @lc code=start
class Solution
{
public:
  int findTargetSumWays(vector<int>& nums, int target)
  {
    // 将nums分为A和B两堆，A中的元素全部添加'+'，B中的元素全部添加'-'
    // 令S = sum(nums), SA = sum(A), SB = sum(B)
    // SA - SB = SA - (S - SA) = target => SA = (S + target) / 2;
    // 问题等价于nums中的元素可以划分成多少个A
    int n = nums.size(), sum = 0;
    for (int& num : nums)
      sum += num;
    if ((sum + target) & 0x1 || sum < target || -sum > target)
      return 0;
    int capacity = (sum + target) / 2;
    // dp[j] 表示在和为j的情况下有dp[j]种方法
    vector<int> dp(capacity + 1);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = capacity; j >= nums[i]; --j)
        dp[j] += dp[j - nums[i]];
    }
    return dp[capacity];
  }
};
// @lc code=end
